﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <algorithm>
#include <ios>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

#include <algorithm>
#include <set>
#include <vector>
#include <unordered_set>
class Solution {
public:
    string tmp;
    vector<int> vis;
    void getAll(string& str, vector<string>& ret, int idx)
    {
        if (idx == str.size())
        {
            ret.push_back(tmp);
            return;
        }

        for (int i = 0; i < str.size(); i++)
        {
            if (vis[i] || (i > 0 && str[i] == str[i - 1] && !vis[i - 1])) continue;
            tmp.push_back(str[i]);
            vis[i] = 1;
            getAll(str, ret, idx + 1);
            vis[i] = 0;
            tmp.pop_back();
        }
    }

    vector<string> Permutation(string str) {
        //该题本质上是一个重复元素全排列，剪枝策略为保证数据是从左往右填入的（排完序）
        vector<string> ret;
        vis.resize(str.size(), 0);
        sort(str.begin(), str.end());
        getAll(str, ret, 0);
        return ret;
    }
};

int main() {
    return 0;
}
// 64 位输出请用 printf("%lld")
//1 1 1
//1 0 0
//1 0 0
//1 0 0